/**
 * 删除链表中所有值为x的结点.
 * 思路:1. 从头到尾依次遍历整个单链表, pre_node指向要node的前驱, 
 * 如果找到要删除的结点delet_node, 则node=node->next, 
 * 否则pre_node和node同时向后移动.
 * 
*/

#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

typedef struct LNode{
    int data;
    struct LNode* next;
}LNode, *LinkedList;

//初始化
bool init(LinkedList &list);

//插入元素
bool insert(LinkedList &list, int data);

//展示当前链表中的元素
void print(LinkedList &list);

//删除操作
void deleteNode(LinkedList &list, int deleteElem);

int main()
{
    LinkedList list=NULL;
    init(list);
    insert(list,1);
    insert(list,2);
    insert(list,3);
    insert(list,2);
    insert(list,3);
    insert(list,4);
    insert(list,2);
    insert(list,2);
    insert(list,6);
    insert(list,9);

    print(list);

    deleteNode(list,2);
    print(list);
    return 0;
}

bool init(LinkedList &list)
{
    //创建一个头结点
    list=(LNode* )malloc(sizeof(LNode));
    if(!list)
        return false;
    list->data=-1;
    list->next=NULL;
    return true;
}

bool insert(LinkedList &list, int data)
{
    //创建一个新的结点
    LNode* newNode=(LNode* )malloc(sizeof(LNode));
    if(!newNode)
        return false;
    
    newNode->data=data;
    newNode->next=NULL;

    LinkedList tmpList=list;
    while(tmpList->next)
    {
        tmpList=tmpList->next;
    }
    tmpList->next=newNode;
    return true;
}

void print(LinkedList &list)
{
    LinkedList tmpList=list;
    if(!tmpList)
        return;

    while(tmpList)
    {
        printf("%d ",tmpList->data);
        tmpList=tmpList->next;
    }
    printf("\n");
}

void deleteNode(LinkedList &list, int deleteElem)
{ 
    if(!list) return;

    LinkedList pre_node=list;       //pre_node结点为遍历结点node的前驱结点
    LinkedList delete_node=NULL;    //delete_node为待删除结点
    LinkedList node=list->next;     //node结点为遍历结点, pre_node->next=node;
    while(node)
    {
        if(node->data==deleteElem)  //如果找到
        {
            delete_node=node;       //锁定delete_node
            node=node->next;        //更改遍历结点node的next指向
            pre_node->next=node;    //更改前驱结点pre_node的next指向
            free(delete_node);      //释放要删除结点的内存  
        } else{
            pre_node=node;
            node=node->next;
        }
    }
}